class Solution:
    def lastRemaining(self, n: int) -> int:
        res = [i for i in range(1, n+1)]
        while len(res) > 1:
            res = [num for index, num in enumerate(res) if index % 2 != 0]
            res.reverse()
            # print(res, len(res))
        return res[0]


from math import floor


class Solution2:
    def lastRemaining(self, n: int) -> int:
        head, count = 1, 0
        while n > 1:
            if count % 2 != 0:
                if n % 2 != 0:
                    head += 2 ** count
            else:
                head += 2 ** count
            n = floor(n / 2)
            count += 1
        return head


a = Solution()
b = Solution2()
for i in range(1, 100):
    res1 = a.lastRemaining(i)
    res2 = b.lastRemaining(i)
    if res1 != res2:
        print("a", i, res1)
        print("b", i, res2)
        print("-" * 30)
a.lastRemaining(99)
b.lastRemaining(99)
